package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/">无重复字符的最长子串(Longest Substring Without Repeating Characters)</a>
 * <p>给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: s = "abcabcbb"
 *      输出: 3
 *      解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 *
 * 示例 2:
 *      输入: s = "bbbbb"
 *      输出: 1
 *      解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 *
 * 示例 3:
 *      输入: s = "pwwkew"
 *      输出: 3
 *      解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *              请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>0 <= s.length <= 5 * 10^4</li>
 *         <li>s 由英文字母、数字、符号和空格组成</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/25 14:03
 */
public class LC0003LongestSubstringWithoutRepeatingCharacters_M {

    static class Solution {
        public int lengthOfLongestSubstring(String s) {
            int length = s.length();
            if (length <= 1) {
                return length;
            }
            int ret = 0;
            // 左边界 i ，保证区间 [i+1,j] 内无重复字符且最大
            int left = 0;
            // 哈希表 dic 统计： 指针 j 遍历字符 s ，哈希表统计字符 s[j] 最后一次出现的索引 。
            Map<Character, Integer> dic = new HashMap<>();
            char[] chars = s.toCharArray();
            // 滑动窗口：保证每个窗口里字母都是唯一的 。
            // 没有重复字母时，调整右边界；当窗口内出现重复字母时，调整左边界
            for (int currIndex = 0; currIndex < length; ++currIndex) {
                char ch = chars[currIndex];
                if (dic.containsKey(ch)) {
                    // 更新左边界至上一次该字母出现位置的下一个位置。此时可以保证[left,currIndex]范围内无重复字符
                    // 可能出现这种情况： bacab。index:4的a上次出现的位置在index:1，index:5的b上次出现的位置在index:0，所以需要取最大值
                    left = Math.max(left, dic.get(ch) + 1);
                }
                // 更新哈希表中当前字母最后一次出现的位置
                dic.put(ch, currIndex);
                // 更新结果： 取上轮 res 和本轮双指针区间 [i+1,j] 的宽度（即 j−i）中的最大值。
                ret = Math.max(ret, currIndex - left + 1);
            }
            return ret;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.lengthOfLongestSubstring("abcabcbb"));
        System.out.println(solution.lengthOfLongestSubstring("bbbbb"));
        System.out.println(solution.lengthOfLongestSubstring("pwwkew"));
        System.out.println(solution.lengthOfLongestSubstring("abba"));
    }

}
